//
//  31.整数中1的出现次数(1~n).swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/21.
//

import Foundation
/*
 题目：输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数
    例如，1~13中包含1的数字有1、10、11、12、13因此共出现6次
 思路：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/mian-shi-ti-43-1n-zheng-shu-zhong-1-chu-xian-de-2/
 举例说明：以216为例，注意216是一个相当特殊的数字，从1到216这216个数中，个位是1的情况有1 11 21 31 41 51 .... 211 ，(注意这个11，这里虽然出现了两个1，但是下一步固定十位为1的时候会考虑到)这里一共有1~21=21 +1(001种) 也就是216/10+1；然后是十位数，11，12，13，14，15...19;(10个) 110，111，112，113...119;(10个) 210，211，212...216(6+1，加1是因为0到6) 这里我们发现，从1到216这216个数中，固定十位数为1的情况有 10*2+6+1，想到这里，我们应该能够理解为什么需要把216这个数字拆分成a=n/m和b=n%m了，因为我们需要单独考虑210到216这7个数，此时(考虑10位数的时候)除了a/2(其实就是百位数）*10=20以外，还要加上b+1；假如n不是216，而是206，则取不到210到216这7个数，假如n是226,则会取到210到219这10个数，由此可见,只有a的末位为1时才需要考虑取不满m个的情况，故a % 10 == 1时，要加上b+1；再考虑n=226的情况，此时由于可以取到210到219这10个数，所以固定十位数为1的情况有(a/10+1)*10；那n=236呢？也是(a/10+1)*10，接着往后想一直到306，都是30，而316是30+7，据此可以判断，只有0/1是特殊的，在程序实现中这么处理这个特殊呢？可以加一个判断，或者用a+8避免这个判断，之所以是+8，通过上面的分析很明显可以理解，是因为当a的次低位为0或者1时，a/10==(a+8)/10，当a的次低位>=2，补8会产生进位位，效果等同于(a/10+1)
 */
func offer_31() {
    print(Solution().numberOf1Between1AndN_Solution(2300))
}
/*
 class Solution {
     public int countDigitOne(int n) {
         int digit = 1, res = 0;
         int high = n / 10, cur = n % 10, low = 0;
         while(high != 0 || cur != 0) {
             if(cur == 0) res += high * digit;
             else if(cur == 1) res += high * digit + low + 1;
             else res += (high + 1) * digit;
             low += cur * digit;
             cur = high % 10;
             high /= 10;
             digit *= 10;
         }
         return res;
     }
 }
 */
fileprivate class Solution {
    func numberOf1Between1AndN_Solution(_ n: Int) -> Int {
        var count = 0
        var i = 1
        var high = 0
        var low = 0
        while i <= n {
            high = n / i
            low = n % i
            count += (high+8)/10*i + (high%10==1 ? low+1 : 0)
            i *= 10
        }
        return count
    }
}
